package leetcode;

//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//示例 1：
//输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//示例 2：
//输入: "cbbd"
//输出: "bb"

public class problems_005 {

    public static void main(String[] args) {
        System.out.println(new Solution().longestPalindrome("babad"));
    }

    static class Solution {
        public String longestPalindrome(String s) {
            if (null == s || "".equals(s)) {
                return "";
            }
            String ret = "";
            for (int i = 0; i < s.length(); i++) {
                String strOdd = findpalindromic(s, i, i);
                String strEven = findpalindromic(s, i, i + 1);
                if(strOdd.length() > ret.length()) ret = strOdd;
                if(strEven.length() > ret.length()) ret = strEven;
            }
            return ret;
        }
        // 回文查询
        private String findpalindromic(String s, int left,int right){
            if(right >= s.length() || s.charAt(left) != s.charAt(right)){
                return "";
            }
            while (left-1 >= 0 && right+1 < s.length() && s.charAt(left-1) == s.charAt(right+1)){
                right++;
                left--;
            }
            return s.substring(left,right+1);
        }
    }

//    public static void main(String[] arge){
//        System.out.println(longestPalindrome("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"));
//    }
//    public static String longestPalindrome(String s) {
//        if(null == s || "".equals(s)){
//            return "";
//        }
//        int index = 0; // 主索引
//        int length = s.length();
//        String ret = String.valueOf(s.charAt(0)); // 返回值
//        // 奇数回文
//        for (int i = 1; i < s.length() -1; i++) {
//            int left = i - 1, right = i + 1;
//            String indexStr = String.valueOf(s.charAt(i)); // 查找值
//            for (; left >= 0 && right <= length-1 ; left--, right++) {
//                if(s.charAt(left) != s.charAt(right)){
//                    break;
//                }
//                indexStr = s.charAt(left) + indexStr + s.charAt(right);
//            }
//            // 判断是否更大
//            if(indexStr.length() >= s.length() / 2) return indexStr;
//            if(indexStr.length() > ret.length()){
//                ret = indexStr;
//            }
//        }
//        // 偶数回文
//        for (int i = 0; i < s.length() -1; i++) {
//            int left = i, right = i + 1;
//            String indexStr = ""; // 查找值
//            for (; left >= 0 && right <= length-1 ; left--, right++) {
//                if(s.charAt(left) != s.charAt(right)){
//                    break;
//                }
//                indexStr = s.charAt(left) + indexStr + s.charAt(right);;
//            }
//            // 判断是否更大
//            if(indexStr.length() >= s.length() / 2) return indexStr;
//            if(indexStr.length() > ret.length()){
//                ret = indexStr;
//            }
//        }
//        return ret;
//    }
}
